package com.company.struct;


import com.company.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/same-tree/
 * @date 2019/11/28 8:27
 * 给定两个二叉树，编写一个函数来检验它们是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 */
public class SameTree {


   public static boolean isSameTree02(TreeNode p, TreeNode q) {

       if (p == null && q == null) return true;
       else if (p == null || q == null) return false;

       if (p.val != q.val) return false;

       return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
   }

    public static boolean isSameTree(TreeNode p, TreeNode q) {

        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.add(p);
        q2.add(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode poll1 = q1.poll();
            TreeNode poll2 = q2.poll();
            if (poll1 == null && poll2 == null) continue;
            else if (poll1 == null || poll2 == null) return false;
            else if (poll1.val != poll2.val) {
                return false;
            }
            q1.add(poll1.left);
            q1.add(poll1.right);
            q2.add(poll2.left);
            q2.add(poll2.right);
        }

        return true;
    }

}
